package q22_generateParenthesis;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Solution_2 {
    public static List<String> generateParenthesis(int n){
        if (n == 1) return Arrays.asList("()");

        HashSet<String> set = new HashSet<>();
        for (String str : generateParenthesis(n - 1)) {
            for (int i = 0; i <= str.length() / 2; i++) {
                set.add(str.substring(0, i) + "()" + str.substring(i, str.length()));
            }
        }
        return new ArrayList<>(set);

    }
}
